package com.major.linkedlist;

import java.util.Stack;

public class SingleLinkedList {
    public static void main(String[] args) {

        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "oujingwei", "区景伟");
        HeroNode hero3 = new HeroNode(3, "limingyang", "李明扬");
        HeroNode hero4 = new HeroNode(4, "4", "4");
        HeroNode hero5 = new HeroNode(5, "5", "5");
        HeroNode hero6 = new HeroNode(6, "6", "6");
        HeroNode updateHero2 = new HeroNode(6, "lihongrui", "李洪睿");

        SingleLinkHero linkHero = new SingleLinkHero();
        SingleLinkHero linkHero2 = new SingleLinkHero();
        linkHero.addHeroByOrder(hero1);
        linkHero.addHeroByOrder(hero3);
        linkHero.addHeroByOrder(hero5);
        linkHero2.addHeroByOrder(hero2);
        linkHero2.addHeroByOrder(hero4);
        linkHero2.addHeroByOrder(hero6);

        SingleLinkHero twoToOne = SingleLinkHero.twoToOne(linkHero.getHead(), linkHero2.getHead());
        twoToOne.showHero();


        //linkHero.update(updateHero2);
        //linkHero.delete(2);

        //linkHero.showHero();
        //SingleLinkHero.reversePrint(linkHero.getHead());
        //SingleLinkHero.reverseLink(linkHero.getHead());
        //linkHero.showHero();


    }
}

class HeroNode {
    int num;
    String name;
    String nickName;
    HeroNode next;

    public HeroNode(int num, String name, String nickName) {
        this.name = name;
        this.nickName = nickName;
        this.num = num;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "num=" + num +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }

    public int getNum() {
        return num;
    }

    public void setNum(int num) {
        this.num = num;
    }
}

class SingleLinkHero {
    private HeroNode head = new HeroNode(0, "", "");

    public HeroNode getHead() {
        return head;
    }

    public void setHead(HeroNode head) {
        this.head = head;
    }

    /**
     * 合并两个有序为一个有序
     *
     * @param head1
     * @param head2
     */
    public static SingleLinkHero twoToOne(HeroNode head1, HeroNode head2) {

        SingleLinkHero linkHero = new SingleLinkHero();

        HeroNode temp = head1.next;
        HeroNode temp2 = head2.next;
        HeroNode next = null;
        HeroNode next2 = null;

        while (temp != null) {
            next = temp.next;
            linkHero.addHeroByOrder(temp);
            temp = next;
        }
        while (temp2 != null) {
            next2 = temp2.next;
            linkHero.addHeroByOrder(temp2);
            temp2 = next2;
        }
        return linkHero;
    }

    /**
     * 逆序打印
     */
    public static void reversePrint(HeroNode head) {
        if (head.next == null) return;

        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;

        // 入栈
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        // 出栈
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }

    /**
     * 单链表反转
     */
    public static void reverseLink(HeroNode head) {
        // 为空或者只有一个结点
        if (head.next == null || head.next.next == null) {
            return;
        }

        // 反转
        HeroNode reverseHead = new HeroNode(0, "", "");
        HeroNode cur = head.next;
        HeroNode next = null; // 很重要的一步

        while (cur != null) {
            next = cur.next;        // *** 暂时保存一下后一个结点，不然就找不到了 ***

            // 这两步 将取出的结点 连接到新链表上
            cur.next = reverseHead.next;    // 后链接
            reverseHead.next = cur;         // 前链接

            cur = next;                     // 后移一位

        }
        // 原来的头结点 连接上来
        head.next = reverseHead.next;


    }

    /**
     * 删除
     */
    void delete(int num) {
        if (head.next == null) {
            System.out.println("链表为空,");
            return;
        }

        HeroNode temp = head;
        boolean flag = false;
        // 遍历找到这个结点
        while (true) {
            if (temp.next == null) {
                break;  // 链表里没有这个编号
            }
            if (temp.next.num == num) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.println("没有找到编号为 " + num + " 的英雄");
        }
    }

    /**
     * 修改信息，根据num
     *
     * @param updateHero
     */
    void update(HeroNode updateHero) {
        // ***** 判断是否为空 *****
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head.next;
        boolean flag = false;
        // ***** 遍历和具体操作分开写 **********************************************************
        // 遍历找到这个结点
        while (true) {
            if (temp.next == null) {
                break;  // 链表里没有这个编号
            }
            if (temp.num == updateHero.num) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = updateHero.name;
            temp.nickName = updateHero.nickName;
        } else {
            System.out.println("没有找到编号为 " + updateHero.num + " 的英雄");
        }
    }

    /**
     * 有顺序添加
     *
     * @param orderNode
     */
    void addHeroByOrder(HeroNode orderNode) {
        // 临时变量
        HeroNode temp = head;
        // 遍历找到要插入的位置
        // 插入节点的 num 小于下一个，
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.num > orderNode.num) { // 找到了要插入的位置
                break;
            }
            temp = temp.next;
        }
        if (orderNode.num == temp.num) {
            System.out.println("该位置有人了");
            return;
        }
        orderNode.next = temp.next;
        temp.next = orderNode;

    }

    /**
     * 无顺序添加
     *
     * @param addHero
     */
    public void addHero(HeroNode addHero) {
        // 临时变量
        HeroNode temp = head;
        // 遍历找到链表最后一个节点
        while (true) {
            if (temp.next == null) {
                temp.next = addHero;
                break;
            }
            // 找到最后一个
            temp = temp.next;
        }
    }

    /**
     * 显示：遍历
     */
    void showHero() {
        // 判断是否为空
        if (head.next == null) {
            System.out.println("empty");
            return;
        }

        // 因为头节点不能动，所以需要temp
        HeroNode temp = head.next;
        while (true) {
            System.out.println(temp);
            if (temp.next == null) {
                break;
            }
            // 节点后移
            temp = temp.next;
        }

    }
}
